package hotLeetcode;

import com.sun.source.tree.IfTree;
import com.sun.source.tree.WhileLoopTree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class H101Leetcode {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    //错误实现
    public boolean isSymmetric2(TreeNode root) {
        Stack<TreeNode> leftstack = new Stack<>();
        Stack<TreeNode> rightstack = new Stack<>();

        if (root.left != null && root.right != null) {
            leftstack.push(root.left);
            rightstack.push(root.right);
        }

        while (!leftstack.isEmpty()) {

            TreeNode left = leftstack.pop();
            TreeNode right = rightstack.pop();

            if (root.left == null && root.right == null) return true;
            if (root.right == null) return false;
            if (root.left == null) return false;

            if (left.val != right.val) return false;
            leftstack.push(left.left);
            leftstack.push(left.right);
            rightstack.push(right.right);
            rightstack.push(right.left);


        }

        return false;

    }


    private Stack<TreeNode> putStack(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty()) {


        }
        return stack;

    }

    public boolean isSymmetric1(TreeNode root) {

        return left_and_right(root.left, root.right);

    }

    private boolean left_and_right(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null) return false;
        if (right == null) return false;
        if (left.val != right.val) return false;

        return left_and_right(left.left, right.right) && left_and_right(left.right, right.left);


    }


    //不用递归 用栈来实现
    public boolean isSymmetric3(TreeNode root) {
        if (root == null) return true;

        Stack<TreeNode> stack = new Stack<>();

        stack.push(root.left);
        stack.push(root.right);

        while (!stack.isEmpty()) {
            TreeNode left = stack.pop();
            TreeNode right = stack.pop();

            if (left == null && right == null) {
                continue;
            }

            if (left == null || right == null || left.val != right.val) return false;

            //放入接下来的
            stack.push(left.left);
            stack.push(right.right);
            stack.push(left.right);
            stack.push(right.left);
        }


        return true;


    }

    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);

        while (!queue.isEmpty()) {
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();

            // 如果两个节点都为空，则继续比较下一对节点
            if (left == null && right == null) {
                continue;
            }
            // 如果其中一个节点为空，或者两个节点的值不相等，则树不是对称的
            if (left == null || right == null || left.val != right.val) {
                return false;
            }

            // 将左节点的右子节点和右节点的左子节点加入队列
            queue.offer(left.right);
            queue.offer(right.left);

            // 将左节点的左子节点和右节点的右子节点加入队列
            queue.offer(left.left);
            queue.offer(right.right);

            // 注意：这里的加入顺序是为了保证在下一轮循环中，
            // left 和 right 变量分别指向当前层的对应节点进行比较
            // 即 left 指向当前层的左子树的左孩子，right 指向当前层的右子树的右孩子，
            // 然后是 left 指向当前层的左子树的右孩子，right 指向当前层的右子树的左孩子。
        }

        // 如果队列为空且没有返回 false，则说明树是对称的
        return true;

    }

}
